package _17_剑指Offer;

public class _64_剑指Offer求12n {

    public static void main(String[] args) {

        _64_剑指Offer求12n v = new _64_剑指Offer求12n();
        System.out.println(v.sumNums(3));
    }

    // a * b, 如果a的二进制第i位为1，那么其对b的贡献就是 a << i
    public int mul(int a, int b) {
        int ans = 0;
        while (b != 0) {
            if ((b & 1) == 1) {
                ans += a;
            }
            a <<= 1;
            b >>= 1;
        }
        return ans;
    }

    // 快速乘法计算，如果是某两个数相乘，那么可以使用加法的移位来实现
    public int sumNums(int n) {
        int ans = 0;
        int other = n + 1;
        if ((n & 1) == 1) {
            ans += other;
        }
        // 移位
        n >>= 1;
        other <<= 1;

        if ((n & 1) == 1) {
            ans += other;
        }
        // 移位
        n >>= 1;
        other <<= 1;

        if ((n & 1) == 1) {
            ans += other;
        }
        // 移位
        n >>= 1;
        other <<= 1;

        if ((n & 1) == 1) {
            ans += other;
        }
        // 移位
        n >>= 1;
        other <<= 1;

        if ((n & 1) == 1) {
            ans += other;
        }
        // 移位
        n >>= 1;
        other <<= 1;

        if ((n & 1) == 1) {
            ans += other;
        }
        // 移位
        n >>= 1;
        other <<= 1;

        if ((n & 1) == 1) {
            ans += other;
        }
        // 移位
        n >>= 1;
        other <<= 1;

        if ((n & 1) == 1) {
            ans += other;
        }
        // 移位
        n >>= 1;
        other <<= 1;

        if ((n & 1) == 1) {
            ans += other;
        }
        // 移位
        n >>= 1;
        other <<= 1;

        if ((n & 1) == 1) {
            ans += other;
        }
        // 移位
        n >>= 1;
        other <<= 1;

        if ((n & 1) == 1) {
            ans += other;
        }
        // 移位
        n >>= 1;
        other <<= 1;

        if ((n & 1) == 1) {
            ans += other;
        }
        // 移位
        n >>= 1;
        other <<= 1;

        if ((n & 1) == 1) {
            ans += other;
        }
        // 移位
        n >>= 1;
        other <<= 1;

        if ((n & 1) == 1) {
            ans += other;
        }
        return ans >> 1;
    }

    // 等差数列求和公式
    public int sumNums2(int n) {
        return (int)(Math.pow(n, 2) + n) >> 1;
    }

    // 利用短路思想求解
    public int sumNums1(int n) {
        boolean flag = n > 0 && (n += sumNums1(n - 1)) > 0;
        return n;
    }

}
